\section{模 $p^{s}$ 原根}

\begin{frame}{原根}

模 $m$ 的整数同余类环 $\mathbb{Z} / m \mathbb{Z}$ 的单位群为
\[
U_{m}=(\mathbb{Z} / m \mathbb{Z})^{*}=\{\bar{a} \mid (a, m)=1,1 \leqslant a<m\},
\]
含 $\varphi(m)$ 个元素 (每个元素是一个同余类). 
\pause
对$\bar{a}\in U_m$,
也记 $\operatorname{ord}(\bar{a})$ 为 $\operatorname{ord}_{m}(a)$, 也称为 \emph{$a$ 模 $m$ 的阶}， 必是 $\varphi(m)$ 的因子。

\pause
如果存在 $g \in \mathbb{Z}$ 使得
\[
U_{m}=\langle\bar{g}\rangle=\left\{1, \bar{g}, \bar{g}^{2}, \cdots, \bar{g}^{\varphi(m)-1}\right\}
\]
则称 $g$ 为模 $m$ 的一个\emph{原根} (primitive root), 也称 $g \left(\mod m\right)$ 或 $\bar{g}$ 为\emph{原根}。 
\pause
``模 $m$ 的原根 $\bar{g}$ 存在'' 意味着 $U_{m}$ 是循环群， 原根 $\bar{g}$ 即是循环群 $U_{m}$ 的生成元。 
\pause
显然， $U_{2}=\{\overline{1}\}$ 和 $U_{4}=\{\overline{1},-\overline{1}\}$ 皆有原根; 此为平凡情形。 
除此之外， 我们将证明只有模 $m=p^{s}$ 或 $2 p^{s}$ 时， 原根存在 ($p$ 为奇素数).

\pause
例如， 模 $m=9, \varphi(9)=6$. 对 $g=2$, 有
\[
  2^{2} \equiv 4,\quad 2^{3} \equiv-1,\quad 2^{4} \equiv-2,\quad 2^{5} \equiv 5,\quad 2^{6} \equiv 1\quad \left(\mod 9\right),
\]
故 $2$ 为模 $9$ 的原根。

\pause
再如， 模 $m=8, \varphi(8)=4.$ $1^{2} \equiv 3^{2} \equiv 5^{2} \equiv 7^{2} \equiv 1 \left(\mod 8\right)$. 故模 $8$ 无原根。
\end{frame}

\begin{frame}

\begin{lemma}
  (1) $g\left( \mod m \right)$ 为原根当且仅当 $g\left( \mod m \right)$ 的阶 $\operatorname{ord}_m (g)=\varphi(m)$. 

  (2) 若模$m$有原根$g$, 则所有 (模$m$意义下) 原根为 
  \[
    \left\{g^{i} \mid(i, \varphi(m))=1, 1\leqslant i<\varphi(m)\right\},
  \]
  (模$m$同余类的) 个数为 $\varphi(\varphi(m))$. 
\end{lemma}
\pause

\begin{proof}
  (1) 若$\bar{g}$为$U_m$的生成元，则$\ord_m(g)=\sharp U_m=\varphi(m)$.
  反过来，设$\ord_m(g)=\varphi(m)=\sharp U_m$.
  $\bar{g}$生成的$U_m$的循环子群$\pair{\bar{g}}$的阶等于$\ord_m(g)$, 从而等于$\sharp U_m$.
  因此$\pair{\bar{g}}$是整个群$U_m$, $U_m$由$\bar{g}$生成，$g$为模$m$原根。

  (2) \S3.1中引理5知$\ord_m(g^i)=\frac{\ord_m(g)}{(i, \ord_m(g))}=\frac{\varphi(m)}{(i, \varphi(m))}$.
  又由(1)知$g^i$是原根当且仅当$\ord_m(g^i)=\varphi(m)$, 当且仅当$(i, \ord_m(g))=1$.
  因此在模$g$的阶$\varphi(m)$的意义下，所有可能的$i$为满足$(i, \varphi(m))=1, 1\leqslant i<\varphi(m)$的$i$.
  由此可知，所有 (模$m$意义下) 原根为 
  $\left\{g^{i} \mid(i, \varphi(m))=1, 1\leqslant i<\varphi(m)\right\}$,
  且个数为$\varphi(\varphi(m))$. 
\end{proof}

\begin{lemma}%系1
 设 $m>1$, $\varphi(m)$ 的所有的不同素因子为 $p_{i}$ ($i=1, \cdots, s$), $(g, m)=1$. 则 $g$ 为模 $m$ 原根的充分必要条件是
 \begin{equation*}
   g^{\frac{\varphi(m) }{ p_{i}}} \not \equiv 1 \quad\left(\mod m\right) \quad(i=1, \cdots, s) \tag{2}
 \end{equation*}
 \end{lemma}
\pause
\end{frame}

\begin{frame}
  \begin{proof}
    $g$ 为模 $m$ 原根相当于其模 $m$ 阶 $\operatorname{ord}_{m}(g)=\varphi(m)$. 因
    $g^{\varphi(m)} \equiv 1\left(\mod m\right)$,
    从而 $\operatorname{ord}_{m}(g) \mid \varphi(m)$. 故假若 $\operatorname{ord}_{m}(g)<\varphi(m)$, 必有
    $\operatorname{ord}_{m}(g) \mid \frac{\varphi(m)}{ p_{i}}$, 对某个 $i$,
    导致 $g^{\frac{\varphi(m)}{ p_{i}}} \equiv 1\left(\mod m\right)$, (2) 式不成立。 又显然 $\operatorname{ord}_{m}(g)=\varphi(m)$ 时 (2) 式成立。证毕。
  \end{proof}

\pause


%\begin{example*}
%  以 $m=p=761$ 为例， $\varphi(m)=760=2^{3} \cdot 5 \cdot 19$. 而
%  $760 / 2=380$, $760 / 5=152$, $760 / 19=40$,
%故需验证 $g^{380}, g^{152}, g^{40}$ 均不同余于 $1\left(\mod 761\right)$.
%
%\pause
%试验 $g=2$ 可否： $2^{380} \equiv 1\left(\mod 761\right)$. 故 $2$ 非原根。
%
%\pause
%试验 $g=3$ 可否： $3^{380} \equiv-1\left(\mod 761\right), 3^{152} \equiv 1\left(\mod 761\right)$. 故 $3$ 非原根。
%
%\pause
%跳过 $4=2^{2}$. 因 ord $a^{r}=\frac{\operatorname{ord} a}{(r, \operatorname{ord} a)} \leqslant \operatorname{ord} a$, 故 $\operatorname{ord}  2^{2} \leqslant \operatorname{ord} 2$. 见 3.1 引理 5.
%
%\pause
%试验 $g=5$ 可否： $3^{380} \equiv 1\left(\mod 761\right)$. 故 $5$ 非原根。
%
%\pause
%试验 $g=6$ 可否： $6^{380} \equiv-1\left(\mod 761\right), 6^{152} \equiv 67\left(\mod 761\right), 6^{40} \equiv-263$ $\left(\mod 761\right)$.
%
%\pause
%故模 $761$ 的最小原根为 $g=6$. 一旦知道一个原根 $g$, 则按引理 1 可得所有原根。
%\end{example*}

\begin{example}
  以 $m=23$ 为例， $\varphi(23)=22=2\cdot 11$. 而
  $22/2=11$, $22/11=2$,
故需验证 $g^{11}, g^{2}$ 均不同余于 $1\left(\mod 23\right)$.

\pause
试验 $g=2$ 可否： $2^{11} \equiv 2048 \equiv 1\left(\mod 23\right)$. 故 $2$ 非原根。

\pause
试验 $g=3$ 可否： $3^{11} \equiv 3^{3\times 3+2}\equiv 27^3\cdot 9\equiv 4^3\cdot 9\equiv  -5\times 9\equiv 1\left(\mod 23\right)$. 故 $3$ 非原根。

\pause
跳过 $4=2^{2}$. 因 ord $a^{r}=\frac{\operatorname{ord} a}{(r, \operatorname{ord} a)} \leqslant \operatorname{ord} a$, 故 $\operatorname{ord}  2^{2} \leqslant \operatorname{ord} 2$. 见 3.1 引理 5.

\pause
试验 $g=5$ 可否： $5^{2} \equiv 2\nequiv 1\left(\mod 23\right)$, 且
\[
  5^{11} \equiv 5^{2\times 5+1}\equiv 25^5\cdot 5\equiv 2^5\cdot 5\equiv 9\cdot 5\equiv -1\nequiv 1\left(\mod 23\right).
\]
故 $5$ 为原根。


\pause
因此模 $23$ 的最小原根为 $g=5$. 
\pause
一旦知道一个原根 $g=5$, 则按引理 1 可得所有原根
为
\[
\begin{aligned}
  \{g^k\mid (k,22)=1, 1\leqslant k<22\}&= \{5, 5^3, 5^5, 5^7, 5^9, 5^{13}, 5^{15}, 5^{17}, 5^{19}, 5^{21}\}\\
& \equiv \{5, 10, 20, 17, 11, 21, 19, 15, 7, 14\}\left( \mod 23 \right).
\end{aligned}
\]
\end{example}
\end{frame}



\begin{frame}{模 $p^{s}$ 或 $2p^s$ 原根}

“模素数 $p$ 的原根存在”最早引起注意， Gauss 在 1801 年《算术研究》中首次给出了两个证明 (并指出 Euler 和 Lambert(兰伯特) 知此事实).

\pause
例如： $p=7$ 时， $\varphi(\varphi(7))=2$, 实际上两个原根为$3$ 和 $5$. 
(例如，$\varphi(7)=6=2\times 3$,
   而$\bar{3}^3=\overline{-1}\neq 1$且$\bar{3}^2=\bar{2}\neq 1$, 
 故$\operatorname{ord}\bar{3}=6$.)
 \pause
   原根 $3$ 具体生成 $(\mathbb{Z} / 7 \mathbb{Z})^{*}$如下：
 \[
   (\mathbb{Z} / 7 \mathbb{Z})^{*}=\left\{\overline{3}^{0}, \overline{3}^{1}, \overline{3}^{2}, \overline{3}^{3}, \overline{3}^{4}, \overline{3}^{5}\right\}=\{\overline{1}, \overline{3}, \overline{2}, \overline{6}, \overline{4}, \overline{5}\}.
 \]
 
 \pause
 在给出模素数$p$原根存在的证明之前，我们先观察下如下的例子。
 \pause
考虑乘法群 $W_{4}=\{1, \mathrm{i},-1,-\mathrm{i}\}\subset \CC^*$ 
(其中 $\mathrm{i}=\sqrt{-1} \in \mathbb{C}$), 各元素的阶分别为 $1,4,2,4$; 
因为有 $4$ 阶元， 故为循环群。
\pause
而乘法群 $(\mathbb{Z} / 8 \mathbb{Z})^{*}=\{\overline{1}, \overline{3}, \overline{5}, \overline{7}\}$中，
各元素的阶分别为 $1,2,2,2$, 没有 $4$ 阶元， 故不是循环群；
实际上，$\CC^*$没有子群同构于$(\mathbb{Z} / 8 \mathbb{Z})^{*}$.
\pause
这其中的深层原因如下。

\begin{theorem}%定理1
(1) 域的有限乘法子群必是循环群。 详言之， 设 $F$ 为一域， $G$ 是 $F$ 中有限个非零元构成的乘法群(运算是域的乘法), 则 $G$ 必是循环群。

 (2) 任一有限域 $F$ 的非零元集 $F^{*}$ 是一个循环群。

  (3) 投 $p$ 为素数， 则 $\mathbb{F}_{p}^{*}$ (即 $U_{p}=(\mathbb{Z} / p \mathbb{Z})^{*}$) 是循环群， 即模 $p$ 的原根存在。且当 $d \mid(p-1)$ 时， $\mathbb{F}_{p}^{*}$ 中 $d$ 阶元个数为 $\varphi(d)$, 模 $p$ 原根个数为 $\varphi(p-1)$ (模 $p$ 意义下).

 (4) 设 $G$ 为 $n$ 阶循环群， 则对任意 $d \mid n, G$ 恰有一个 $d$ 阶子群且是循环群， $d$ 阶元的个数为 $\varphi(d)$. 特别， $G$ 的生成元(即 $n$ 阶元) 个数为 $\varphi(n)$.
 \end{theorem}
\end{frame}

\begin{frame}

   \begin{proof}
    (1) 设域 $F$ 的子群 $G$ 为 $n$ 阶。 则 $G$ 中元素的阶都整除 $n$. 记 $d$ 阶元个数为 $\psi(d)$, 则 $\sum_{d \mid n} \psi(d)=n$ (啊， $\psi$ 竟然和 Euler函数 $\varphi$ 满足的等式 $\sum_{d \mid n} \varphi(d)=n$ 一样?!).

\pause
  现在任意固定整数 $d \mid n$, 则有两种情形： $\psi(d) \neq 0$ 或 $\psi(d)=0$.

  \pause
我们断言： $\psi(d) \neq 0$ 时 $\psi(d)=\varphi(d)$.
事实上， $\psi(d) \neq 0$ 意味着存在 $a \in G$ $\subset F$ 为 $d$ 阶，
它生成循环子群 $\langle a\rangle$, 其 $d$ 个元素 $x \in G$ 皆满足 $x^{d}=1$, 
故皆为 $f(x)=x^{d}-1$ 的根， 而且是 $f$ 在 $F$ 中的全部根 ( $d$ 次多项式在域中最多有 $d$ 个根).
\pause 
   于是知， $G$ 中任何 $b \notin\langle a\rangle$ 均非 $f$ 的根， 故非 $d$ 阶元。
   所以 $G$ 中 $d$ 阶元皆在 $\langle a\rangle$中， 恰有 $\varphi(d)$ 个(上节引理 6), 即
  $\psi(d)=\varphi(d).$
断言得证。

\pause
现假若存在某 $d^{\prime} \mid n$ 使 $\psi\left(d^{\prime}\right)=0$, 则因为 $\psi(d)=\varphi(d)($ 当 $\psi(d) \neq 0)$, 故
\[
  \sum_{d \mid n} \psi(d)<\sum_{d \mid n} \varphi(d)=n,
\]
与开始所言 $\sum_{d \mid n} \psi(d)=n$ 矛盾。
\pause
这就证明了： 对任意 $d \mid n$, 均有 $\psi(d)=\varphi(d)$.
\pause
特别可知， $\psi(n)=\varphi(n) \neq 0$, 即 $n$ 阶元个数 $\psi(n)$ 非零， 从而 $G$ 是循环群。


\pause
  (2) 有限域 $F$ 的非零元集 $F^{*}$ 是一个有限乘法群。 故由 (1) 知， $F^{*}$ 是循环群。

 (3) 是 (2) 或 (1) 的特例。

 \pause
 (4) 等同$n$阶循环群$G$为复数域中$n$次单位根构成的乘法群。
 从(1)的证明可知， 对任意 $d \mid n, G$ 恰有一个 $d$ 阶子群 (由$x^d-1\in \CC[x]$的$d$个根构成，即$d$次单位根构成的乘法群) 且是循环群， 
 $G$ 的 $d$ 阶元 (即$d$次本原单位根) 的个数为 $\varphi(d)$.
 \end{proof}

 \end{frame}

\begin{frame}
附录 7.1 表中， 列出了模素数 $p \leqslant 4057$ 的最小原根 $g$ 表。 从中可见， $g=2$是许多 $p$ 的原根， 是不是无限多 $p$ 的原根呢? ---这是未解决的问题。

 E. Artin(阿廷)曾猜想：任一非完全平方正整数 $a$ ($>1$) 必是无限多素数的原根。


 \pause
 下面我们来证明$p$为奇素数时模$p^s$和模$2p^s$原根存在。
 \begin{lemma}%引理1
 (1) 设 $p$ 为任意素数， $k \geqslant 1, a \equiv b\left(\mod p^{k}\right)$, 则
 \[
   a^{p} \equiv b^{p} \quad\left(\mod p^{k+1}\right).
 \]

 (2) 若素数 $p \neq 2, k \geqslant 2$, 则 $(1+c p)^{p^{k-2}} \equiv 1+c p^{k-1}\left(\mod p^{k}\right)$ (对任意 $c \in \mathbb{Z}$).

(3) 若素数 $p \neq 2, p \nmid c$, 则 $1+c p\left(\mod p^{k}\right)$ 的阶为 $p^{k-1}$.
\end{lemma}

\pause
  \begin{proof}
   (1) 记 $a=b+c p^{k}, c \in \mathbb{Z}$, 则
 \[
   a^{p}=b^{p}+\binom{p}{1} b^{p-1} c p^{k}+\binom{p}{2} b^{p-2} c^{2} p^{2 k}+\cdots+c^{p} p^{p k} \equiv b^{p} \quad\left(\mod p^{k+1}\right).
 \]
 这里用到： 当 $1 \leqslant k \leqslant p-1$ 时， $\binom{p}{k} \equiv 0 \left(\mod p\right)${\verify}. %这是因为
 %\[
 %\binom{p}{k}=\frac{p!}{k!(p-k)!} \in \mathbb{Z}
 %\]
 %分母中的素因子都小于 $p$, 故分子中的素数 $p$ 不可能被分母约去， 故知 $p \mid \binom{p}{k}$.

 \pause
  (2) 对 $k$ 归纳。 当 $k=2$ 显然成立。 假设引理对 $k \geqslant 2$ 成立， 对此假设用 (1)的结论， 知
\[
  (1+c p)^{p^{k-1}} \equiv\left(1+c p^{k-1}\right)^{p} \quad\left(\mod p^{k+1}\right).
\]
 \end{proof}
 \end{frame}

 \begin{frame}
   \begin{proof}[续]
右边展开， 得到
\[
  \left(1+c p^{k-1}\right)^{p}=1+\binom{p}{1} c p^{k-1}+\binom{p}{2} c^{2} p^{2(k-1)}+\cdots+c^{p} p^{p(k-1)}.
\]
\pause
除前两项和末项外， 各项皆含因子 $p^{1+2(k-1)}$ (因 $p \mid \binom{p}{r}$ (当 $1 \leqslant r<p$)), 且 $k \geqslant 2$ 表明
$1+2(k-1) \geqslant k+1$, 因此这些项是$p^{k+1}$的倍。
$p \geqslant 3$表明 $p(k-1) \geqslant k+1$, 故最后一项是$p^{k+1}$的倍。
\pause
这样
\[
  (1+c p)^{p^{k-1}} \equiv 1+c p^{k} \quad\left(\mod p^{k+1}\right).
\]

\pause
 (3) 由 (2) 知 $(1+c p)^{p^{k-1}} \equiv 1+c p^{k}\left(\mod p^{k+1}\right)$, 故 
 \[
   (1+c p)^{p^{k-1}} \equiv 1\left(\mod p^{k}\right).
 \]
 而因
 $p \nmid c$, 有
 \[
   (1+c p)^{p^{k-2}} \equiv 1+c p^{k-1} \not \equiv 1\left(\mod p^{k}\right).
 \]
 \end{proof}

 \pause
   \begin{theorem}%定理2
   设 $p$ 为奇素数， 则模 $p^{s}$ 和 $2 p^{s}$ 有原根， 即
 \[
   U_{p^{s}}=\left(\mathbb{Z} / p^{s} \mathbb{Z}\right)^{*} \quad \text {和}\quad U_{2 p^{s}}=\left(\mathbb{Z} / 2 p^{s} \mathbb{Z}\right)^{*}.
 \]
 为循环群 ($s$ 为任意正整数).
 \end{theorem}
\end{frame}

 \begin{frame}
 \begin{proof}
  由孙子分解知，我们有群同构 $U_{2 p^{s}} \cong U_{2} \times U_{p^{s}}=\{1\} \times U_{p^{s}} \cong U_{p^{s}}$, 故只需证 $U_{p^{s}}$ 为循环群。
  \pause
由定理 1, 设 $U_{p}=\langle\bar{g}\rangle$, 不妨设
\[
g^{p-1} \not \equiv 1 \quad\left(\mod p^{2}\right);
\]
否则令 $g^{\prime}=g+p$, 有 
\[
  g^{\prime p-1} \equiv g^{p-1}+(p-1) g^{p-2} p \equiv 1+(p-1) g^{p-2} p \not \equiv 1\left(\mod p^{2}\right),
\]
故用$g'$替换$g$即可。
\pause
我们断言， 此模 $p$ 的原根 $g$ 可为模 $p^{s}$ 的原根。 我们已知$g^{\varphi(p^s)}\equiv 1\left( \mod p^s \right)$, 只需再证明： 若 $g^{n} \equiv 1 \left(\mod p^{s} \right)$, 则
\[
  \varphi\left(p^{s}\right)=p^{s-1}(p-1) \mid n.
\]
\pause
因 $g$ 模 $p$ 的阶为 $p-1$, 故 $g^{p-1}=1+c p$, 且
$g^{p-1} \not \equiv 1\left( \mod p^2 \right)$ 表明$p \nmid c$. 
由上述引理知 $1+c p\left(\mod p^{s}\right)$的阶为 $p^{s-1}$. 故若 $g^{n} \equiv 1\left(\mod p^{s}\right)$, 则
\[
  (1+c p)^{n}=g^{n(p-1)} \equiv 1 \quad\left(\mod p^{s}\right).
\]
从而 $p^{s-1} \mid n$. 
\pause
记 $n=p^{s-1} n_{1}$, 则
\[
  1 \equiv g^{n}=g^{p^{s-1} n_{1}} \equiv g^{n_{1}} \left(\mod p\right)\quad \left(\text{因~} g^{p} \equiv g \left(\mod p\right)\right).
\]
故 $(p-1) \mid n_{1}$. 
\pause
得 $p^{s-1}(p-1) \mid n$.
\end{proof}
\end{frame}

\begin{frame}
 \begin{corollary}%系1
 令$p$为奇素数，$k$为正整数。

 (1) 令 $g$ 为模 $p$ 的一个原根。若 $g^{p-1} \not \equiv 1\left(\mod p^{2}\right)$, 则 $g$ 为模 $p^{k}$ 原根；
 否则， $g+p$ 为模 $p^{k}$ 原根。

 (2) 令 $g$ 为模 $p^k$ 的一个原根。若$g$为奇数， $g$ 为模 $2 p^{k}$ 原根；否则，$g+p^{k}$ 为模 $2 p^{k}$ 原根。
 另外，$g+(g-1) p^{k}$ 总是模 $2 p^{k}$ 原根。
 \end{corollary}

\pause
 \begin{proof}

   (1) 由上述定理的证明立得。
  \pause

  (2) 我们应用群同构 (孙子分解)
  \[
    \sigma\colon U_{2 p^{k}} \rightarrow \{1\} \times U_{p^{k}}, \quad \bar{x}\mapsto (\bar{x}, \bar{x}).
  \]
  于是，$g'$为模$2p^k$原根当且仅当其像$(\overline{g'}, \overline{g'})\in \{1\} \times U_{p^{k}}$为生成元，
  当且仅当$g'\equiv 1\left( \mod 2 \right)$且$g'$为模$p^k$原根。 
  \pause
  特别地，满足 $g^{\prime} \equiv 1 \left(\mod 2\right)$, 且
  $g^{\prime} \equiv g\left(\mod p^{k}\right)$ 的 $g^{\prime}$ 均可。
  \pause
  这样，若$g$为奇数， $g$ 为模 $2 p^{k}$ 原根；否则，$g+p^{k}$ 为模 $2 p^{k}$ 原根。
  \pause
  另外，$g+(g-1)p^k$为奇数，且 $g+(g-1)p^k\equiv g\left( \mod p^k \right)$, 
  故$g+(g-1)p^k$为模$p^k$的一个原根。
\end{proof}

\pause
例如， 模 $3$ 原根为 $2$, 模 $6$ 原根为 $2+3=5$. 模 $5$ 原根为 $2$ (或 $3$), 模 $10$ 原根为 $2+5=7$ (或 $3 \equiv 3+2 \cdot 5$).

\pause
下节将证明， $m=p^{s}, 2 p^{s}, 2,4$ 是仅有的模 $m$ 原根存在情形。

\end{frame}

\begin{frame}
 
\begin{remark*}[附记]
“模 $p$ 有原根”（即上节定理 1(3))有基本的重要性。 此处再给两个证明。
\end{remark*}

\begin{proof*}[另证 1 (用到 Möbius 反演， 见本章最后一节)] $(\mathbb{Z} / p \mathbb{Z})^{*}$ 是 $p-1$ 阶乘法群， 将其元素按阶分类， 其中 $\delta$ 阶元的总数记为 $\psi(\delta)$ (只有 $\delta \mid(p-1)$ 时才有 $\psi(\delta) \neq 0)$.

注意， $\mathbb{F}_{p}$ 中 $p-1$ 个非零元都是 $X^{p-1}-\overline{1}$ 的根 (Fermat 小定理), 故
\[
X^{p-1}-\overline{1}=(X-\overline{1}) \cdots[X-\overline{(p-1)}]
\]
设 $d \mid(p-1)$, 则 $\left(X^{d}-\overline{1}\right) \mid\left(X^{p-1}-\overline{1}\right)$, 故 $X^{d}-\overline{1}$ 在 $\mathbb{F}_{p}$ 中恰有 $d$ 个根（即为满足 $x^{d}=\overline{1}$ 的 $x \in \mathbb{F}_{p}$ 全体), 构成一个群 $W_{d}$, 其中元素的阶均为 $d$ 的因子， 故
\[
\sum_{\delta \mid d} \psi(\delta)=d
\]
用 Möbius 反演， 得到
\[
\psi(d)=\sum_{\delta \backslash d} \mu(\delta) d / \delta=\varphi(d)
\]
右方等号因 \S3.6 系 3 , 即 $\varphi=\mu * \operatorname{Id}$. 特别可知， $\psi(p-1)=\varphi(p-1)>1$ (当 $p>2$), 也就是说 $p-1$ 阶元总是存在的。 由此也知， $(\mathbb{Z} / p \mathbb{Z})^*$ 中 $\delta$ 阶元的总数为 $\psi(\delta)=\varphi(\delta)$.
\end{proof*}
\end{frame}


\begin{frame}
  \begin{proof*}[另证 2]
    设 $p-1=q_{1}^{e_{1}} q_{2}^{e_{2}} \cdots q_{s}^{e_{s}}$ 为 $p-1$ 的素因子分解。 记 $q_{1}=q, e_{1}=e$, 考虑 $\mathbb{F}_{p}$上的方程式：
  \[
\text {  (i)~} X^{q^{\varepsilon-1}} \equiv \overline{1} ; \quad \text { ii)~} X^{q^{\varepsilon}} \equiv \overline{1}
\]
因为 $q^{e} \mid(p-1)$, 故二式均有解， 解数分别为 $q^{e-1}$ 和 $q^{e}$, 故存在 $\bar{g}_{1}$ 是 (ii) 的解而非 $(\mathrm{i})$ 的解， $\operatorname{ord}\left(\bar{g}_{1}\right)=q_{1}^{e_{1}}$. 如此则取得 $g_{i}$ 使得 $\operatorname{ord}\left(\bar{g}_{i}\right)=q_{i}^{e_{i}}(i=1, \cdots, s)$. 令
\[
\bar{g}=\bar{g}_{1} \bar{g}_{2} \cdots \bar{g}_{s}
\]
因
\[
\operatorname{ord}\left(\bar{g}_{i}\right)=q_{i}^{e_{i}}
\]
两两互素， 故由 §3.1 引理 5 得
\[
\operatorname{ord}(\bar{g})=\operatorname{ord}\left(\bar{g}_{1} \cdots \bar{g}_{s}\right)=\operatorname{ord}\left(\bar{g}_{1}\right) \cdots \operatorname{ord}\left(\bar{g}_{s}\right)=q_{1}^{e_{1}} \cdots q_{s}^{e_{s}}=p-1
\]
即 $g=g_{1} g_{2} \cdots g_{s}$ 为模 $p$ 原根。
\end{proof*}

\end{frame}


\begin{frame}{小结}
  \begin{enumerate}
    \item 何为模$m$的一个原根？等价条件有哪些？
    \item 若模$m$原根存在，(模$m$不同的) 原根有多少个？如何从一个原根得到所有原根？
    \item 若模$m$原根存在，如何找到模$m$的最小原根？
    \item 说说域的有限乘法子群的结构。并解释为何。
    \item $n$阶循环群的子群结构如何？每个可能的阶的子群有几个？
    \item $n$阶循环群的生成元有几个？正整数$d$能作为其中元素的阶的等价条件是什么？$d$阶元 (存在的话) 有几个？
    \item 令$p$为奇素数。如何从模$p$原根得到模$p^k$原根？
    如何从模$p^k$原根得到模$2p^k$原根？
  \end{enumerate}
\end{frame}

